package ch2.part2;

/**
 * 自定义的链表结构，包含插入、删除、查找、更新、输出等方法及场景
 * 时间复杂度：
 * - 插入 O(1)
 * - 删除 O(1)
 * - 查询 O(n)
 * - 更新 O(1)
 * - 遍历 O(n)
 *
 * @author liuwanxiang
 * @version 2019/05/14
 */
public class MyLinkedList {

    private Node head;
    private Node end;
    private int size;

    /**
     * 插入<不考虑查询的时间复杂度来看>
     * 时间复杂度: O(n)=1
     *
     * @param index
     * @param data
     */
    public void insert(int index, Integer data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标越界~");
        }
        Node insertNode = new Node(data);
        if (size == 0) {
            head = insertNode;
            end = insertNode;
        } else if (size == index) {
            end.next = insertNode;
            end = insertNode;
        } else if (0 == index) {
            insertNode.next = head;
            head = insertNode;
        } else {
            Node prev = getNode(index - 1);
            insertNode.next = prev.next;
            prev.next = insertNode;
        }
        size++;
    }

    /**
     * 删除<不考虑查询的时间复杂度来看>
     * 时间复杂度: O(n)=1
     *
     * @param index
     * @return
     */
    public Integer delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界~");
        }
        Node deleteNode;
        if (index == 0) {
            deleteNode = head;
            head = head.next;
        } else if (index == size - 1) {
            Node prevNode = getNode(index - 1);
            deleteNode = end;
            prevNode.next = null;
            end = prevNode;
        } else {
            Node prevNode = getNode(index - 1);
            deleteNode = prevNode.next;
            prevNode.next = deleteNode.next;
        }
        size--;
        return deleteNode.data;
    }

    /**
     * 获取某下标的节点元素
     * 时间复杂度: O(n)=n
     *
     * @param index
     * @return
     */
    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界~");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 获取某下标的节点数据
     * 时间复杂度: O(n)=n
     *
     * @param index
     * @return
     */
    public Integer get(int index) {
        return getNode(index).data;
    }

    /**
     * 更新元素<不考虑查询的时间复杂度来看>
     * 时间复杂度: O(n)=1
     *
     * @param index
     * @param data
     * @return
     */
    public Integer update(int index, Integer data) {
        Node node = getNode(index);
        Integer rst = node.data;
        node.data = data;
        return rst;
    }

    /**
     * 打印输出
     * 时间复杂度: O(n)=n
     */
    public void output() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data);
            System.out.print(" ");
            node = node.next;
        }
        System.out.print("\n");
    }

    private static class Node {
        Integer data;
        Node next;

        public Node(Integer data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        // 3
        myLinkedList.insert(0, 3);
        // 4 3
        myLinkedList.insert(0, 4);
        // 4 3 9
        myLinkedList.insert(2, 9);
        // 4 3 9 5
        myLinkedList.insert(3, 5);
        // 4 6 3 9 5
        myLinkedList.insert(1, 6);
        // 6 3 9 5
        myLinkedList.delete(0);
        // 6 3 9 5
        myLinkedList.output();
        // 6 8 9 5
        System.out.println(myLinkedList.update(1, 8));
        // 6 8 9 5
        System.out.println(myLinkedList.get(1));
    }

}
